/**
 * @file binary_search_tree.hpp
 * @author 逆流 (1171267147@qq.com)
 * @brief BST: 对于每个节点，其左子树中的所有节点的值都小于该节点的值，而其右子树中的所有节点的值都大于该节点的值。
 * @version 0.1
 * @date 2024-10-15
 *
 * @copyright Copyright (c) 2024
 *
 */

#ifndef INC_STL_BINARY_SEARCH_TREE_HPP_
#define INC_STL_BINARY_SEARCH_TREE_HPP_

#include "binary_tree.hpp"

namespace stl {

template <typename T>
class BinarySearchTree : public BinaryTree<T> {
public:
    BinarySearchTree() {
        this->root_ = nullptr;
        this->size_ = 0;
    }

    ~BinarySearchTree() { BinaryTree<T>::Remove(this->root_); }

    void Push(T data) override {
        auto cmp = [](const T& lhs, const T& rhs) {
            return lhs < rhs;
        };
        Push(data, cmp);
    }

    void Push(T data, std::function<bool(const T&, const T&)> cmp) {
        if (nullptr == cmp) {
            throw std::logic_error("Must set compare funtion!");
        }
        auto new_node = new BinaryTreeNode<T>(data);
        if (this->Empty()) {
            this->root_ = new_node;
        } else {
            auto current = this->root_;
            while (true) {
                if (cmp(data, current->data)) {
                    if (current->left == nullptr) {
                        current->left = new_node;
                        break;
                    }
                    current = current->left;

                } else {
                    if (current->right == nullptr) {
                        current->right = new_node;
                        break;
                    }
                    current = current->right;
                }
            }
        }
        this->size_++;
    }

    T Pop() override {
        if (this->Empty()) {
            throw std::out_of_range("BinarySearchTree is empty!");
        }
        auto data    = this->root_->data;
        auto current = this->root_;
        while (true) {
            if (current->left == nullptr) {
                this->root_ = current->right;
                break;
            }
            current = current->left;
        }
        delete current;
        this->size_--;
        return data;
    }

    void Clear() override { BinaryTree<T>::Remove(this->root_); }
};
}  // namespace stl
#endif  // INC_STL_BINARY_SEARCH_TREE_HPP_
